<!DOCTYPE HTML>
<html>
<head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8"/>
    <meta name="google-site-verification" content="KEatQX-J4dYY-6J2KU_aP5X8gAJ8wS0lhylI8umX6WA" />
    <meta name="viewport" content="width=device-width,initial-scale=1,minimal-ui">
    <link rel="shortcut icon" href="../images/favicon.ico">
    <link rel="stylesheet" href="../css/code.css" type="text/css"/>
    <link rel="stylesheet" href="../css/bootstrap.css" type="text/css"/>
    <link rel="stylesheet" href="../css/main.css" type="text/css"/>
    <title>编程小梦| 算法之美——二分法</title>
</head>
<body>
<nav class="navbar navbar-default navbar-static-top" style="opacity: .9" role="navigation">
    <div class="container-fluid">
        <div class="navbar-header">
            <button type="button" class="navbar-toggle" data-toggle="collapse"
                    data-target="#bs-example-navbar-collapse-1">
                <span class="sr-only">Toggle navigation</span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </button>
            <a class="navbar-brand" href="/">编程小梦</a>
        </div>
        <div class="collapse navbar-collapse" id="bs-example-navbar-collapse-1">
            <ul class="nav navbar-nav navbar-right">
                <li class="active"><a href="/">Blog</a></li>
                
                <li><a href="https://github.com/kangkaisen" target="_blank" rel="nofollow">GitHub</a></li>
                
                
                <li><a href="http://weibo.com/533234148" target="_blank" rel="nofollow">WeiBo</a></li>
                
            </ul>
        </div>
    </div>
</nav>
<div class="row" style="padding-top: 60px">
    <div class="container center-block">
        <div class="col-md-1"></div>
        <div class="col-md-10 col-sm-12">
            <h1>  算法之美——二分法</h1>
            <hr/>
            <p>作者: 康凯森</p>
            <p>日期: 2016-06-16</p>
            <p>分类: <a href="../tag/算法.html" target="_blank" >算法</a></p>
            <hr/>
            <!-- toc -->
<ul>
<li><a href="#什么时候用二分">什么时候用二分？</a></li>
<li><a href="#二分法模板的四点要素">二分法模板的四点要素</a></li>
<li><a href="#二分法关键">二分法关键</a></li>
<li><a href="#classical-binary-search">classical-binary-search</a></li>
<li><a href="#first-position-of-target">first-position-of-target</a></li>
<li><a href="#last-position-of-target">last-position-of-target</a></li>
<li><a href="#search-insert-position">search-insert-position</a></li>
<li><a href="#search-a-2d-matrix">search-a-2d-matrix</a></li>
<li><a href="#search-a-2d-matrix-ii">search-a-2d-matrix-ii</a></li>
<li><a href="#search-in-a-big-sorted-array">search-in-a-big-sorted-array</a></li>
<li><a href="#find-minimum-in-rotated-sorted-array">find-minimum-in-rotated-sorted-array</a></li>
<li><a href="#find-minimum-in-rotated-sorted-array-ii">find-minimum-in-rotated-sorted-array-ii</a></li>
<li><a href="#find-peak-element">find-peak-element</a></li>
<li><a href="#first-bad-version">first-bad-version</a></li>
<li><a href="#search-in-rotated-sorted-array">search-in-rotated-sorted-array</a></li>
<li><a href="#search-for-a-range">search-for-a-range</a></li>
<li><a href="#total-occurrence-of-target">total-occurrence-of-target</a></li>
<li><a href="#closest-number-in-sorted-array">closest-number-in-sorted-array</a></li>
<li><a href="#k-closest-numbers-in-sorted-array">k-closest-numbers-in-sorted-array</a></li>
<li><a href="#wood-cut">wood-cut</a></li>
<li><a href="#sqrtx">sqrtx</a></li>
<li><a href="#参考资料">参考资料</a></li>
</ul>
<!-- toc stop -->
<h3 id="什么时候用二分？">什么时候用二分？</h3>
<ul>
<li><code>O(logn)</code>的时间复杂度</li>
<li>有序数组</li>
</ul>
<h3 id="二分法模板的四点要素">二分法模板的四点要素</h3>
<ul>
<li>start + 1 &lt; end </li>
<li>start + (end - start) / 2 </li>
<li>A[mid] ==, &lt;, &gt; </li>
<li>A[start] A[end] ? target </li>
</ul>
<h3 id="二分法关键">二分法关键</h3>
<ul>
<li>头尾指针，取中点，判断往哪儿走</li>
<li>寻找满足某个条件第一个或是最后一个位置</li>
<li>保留剩下来一定有解的那一半</li>
</ul>
<h3 id="classical-binary-search">classical-binary-search</h3>
<p>在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1</p>
<pre><code>public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int findPosition(int[] A, int target) {
        // Write your code here
        if (A == null || A.length == 0){
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (target == A[mid]) {
                end = mid;
            } else if (target &gt; A[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == A[start]) {
            return start;
        }
        if (target == A[end]) {
            return end;
        }
        return -1;
    }
}
</code></pre><h3 id="first-position-of-target">first-position-of-target</h3>
<p>在有序数组中查找元素，返回第一个位置。</p>
<pre><code>class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (target == nums[mid]) {
                end = mid;
            } else if (target &gt; nums[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == nums[start]) {
            return start;
        }
        if (target == nums[end]) {
            return end;
        }
        return -1;
    }
}
</code></pre><h3 id="last-position-of-target">last-position-of-target</h3>
<p>给一个升序数组，找到target最后一次出现的位置，如果没出现过返回-1</p>
<pre><code>public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int lastPosition(int[] A, int target) {
        // Write your code here
        if (A == null || A.length == 0){
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (target == A[mid]) {
                start = mid;
            } else if (target &gt; A[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == A[end]) {
            return end;
        }
        if (target == A[start]) {
            return start;
        }
        return -1;
    }
}
</code></pre><h3 id="search-insert-position">search-insert-position</h3>
<p>搜索插入位置</p>
<pre><code>public class Solution {
    /** 
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
    //  find the first position &gt;= target
    public int searchInsert(int[] A, int target) {
        // write your code here
        if (A == null || A.length == 0){
            return 0;
        }
        int start = 0;
        int end = A.length - 1;
        while (start + 1 &lt; end){
            int mid = start + (end - start) / 2;
            if (target == A[mid]) {
                return mid;
            } else if (target &lt; A[mid]){
                end = mid;
            } else {
                start = mid;
            }
        }
        if (target &lt;= A[start]) {
            return start;
        } else if (target &lt;= A[end]) {
            return end;
        } else {
            return end + 1;
        }
    }
}
</code></pre><h3 id="search-a-2d-matrix">search-a-2d-matrix</h3>
<p>写出一个高效的算法来搜索 m × n矩阵中的值。</p>
<p>这个矩阵具有以下特性：</p>
<ul>
<li>每行中的整数从左到右是排序的。</li>
<li>每行的第一个数大于上一行的最后一个整数。</li>
</ul>
<pre><code>public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        boolean found = false;
        if (matrix == null || matrix.length == 0){
            return found;
        }
        int row = matrix.length;
        int column = matrix[row - 1].length - 1;
        int i = 0;
        while (i &lt; row &amp;&amp; column &gt;= 0){
            if (target == matrix[i][column]) {
                return found = true;
            } else if (target &lt; matrix[i][column]) {
                column --;
            } else {
                i ++;
            }
        }
        return found;
    }
}
</code></pre><h3 id="search-a-2d-matrix-ii">search-a-2d-matrix-ii</h3>
<p>写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。</p>
<p>这个矩阵具有以下特性：</p>
<ul>
<li>每行中的整数从左到右是排序的。</li>
<li>每一列的整数从上到下是排序的。</li>
<li>在每一行或每一列中没有重复的整数。</li>
</ul>
<pre><code>public class Solution {
    /**
     * @param matrix: A list of lists of integers
     * @param: A number you want to search in the matrix
     * @return: An integer indicate the occurrence of target in the given matrix
     */
    public int searchMatrix(int[][] matrix, int target) {
        // write your code here
        if (matrix == null || matrix.length == 0){
            return 0;
        }
        int count = 0;  
        int row = matrix.length;
        int column = matrix[row - 1].length;
        int i = 0;
        while (i &lt; row &amp;&amp; column &gt; 0){
            if (matrix[i][column - 1] == target){
                count ++;
                column --;
            }
            else if (matrix[i][column - 1] &gt; target)
                column --;
            else
                i ++;
        }
        return count;
    }
}
</code></pre><h3 id="search-in-a-big-sorted-array">search-in-a-big-sorted-array</h3>
<p>给一个按照升序排序的正整数数组。这个数组很大以至于你只能通过固定的接口 <code>ArrayReader.get(k)</code> 来访问第k个数。并且你也没有办法得知这个数组有多大。找到给出的整数target第一次出现的位置。你的算法需要在O(logk)的时间复杂度内完成，k为target第一次出现的位置的下标。</p>
<p>如果找不到target，返回-1。</p>
<pre><code>/**
 * Definition of ArrayReader:
 * 
 * class ArrayReader {
 *      // get the number at index, return -1 if not exists.
 *      public int get(int index);
 * }
 */
public class Solution {
    /**
     * @param reader: An instance of ArrayReader.
     * @param target: An integer
     * @return : An integer which is the index of the target number
     */
    public int searchBigSortedArray(ArrayReader reader, int target) {
        // write your code here
        int index = 1;
        while (reader.get(index - 1) &lt; target &amp;&amp; reader.get(index - 1) != -1) {
            index = index * 2;
        }
        int start = 0;
        int end = index - 1;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (target == reader.get(mid)) {
                end =  mid;
            } else if (target &gt; reader.get(mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == reader.get(start)) {
            return start;
        }
        if (target == reader.get(end)) {
            return end;
        }
        return -1;
    }
}
</code></pre><h3 id="find-minimum-in-rotated-sorted-array">find-minimum-in-rotated-sorted-array</h3>
<p>假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。</p>
<p>你需要找到其中最小的元素。</p>
<p>你可以假设数组中不存在重复的元素。</p>
<pre><code>public class Solution {
    /**
     * @param num: a rotated sorted array
     * @return: the minimum number in the array
     */
     public int findMin(int[] num) {
        int start = 0;
        int end = num.length - 1;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (num[mid] &gt;= num[end]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (num[start] &lt; num[end]) {
            return num[start];
        } else {
            return num[end];
        }
    }
}
</code></pre><h3 id="find-minimum-in-rotated-sorted-array-ii">find-minimum-in-rotated-sorted-array-ii</h3>
<p>假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。</p>
<p>你需要找到其中最小的元素。</p>
<p>数组中可能存在重复的元素。</p>
<pre><code>public class Solution {
    /**
     * @param num: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] num) {
        int start = 0; 
        int end = num.length - 1;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (num[start] == num[end] &amp;&amp; num[start] == num[mid])
                return findInOrder(num); //退化到顺序查找
            else if (num[mid] &gt;= num[end]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (num[start] &lt; num[end]) {
            return num[start];
        } else {
            return num[end];
        }
    }
    private int findInOrder(int[] num) {
        int min = num[0];
        for (int i = 1; i &lt; num.length; i++) {
            if (num[i] &lt; min)
                min = num[i];
        }
        return min;
    }
}
</code></pre><h3 id="find-peak-element">find-peak-element</h3>
<p>你给出一个整数数组(size为n)，其具有以下特点：</p>
<p>相邻位置的数字是不同的
<code>A[0] &lt; A[1] 并且 A[n - 2] &gt; A[n - 1]</code>
假定P是峰值的位置则满足<code>A[P] &gt; A[P-1]</code>且<code>A[P] &gt; A[P+1]</code>，返回数组中任意一个峰值的位置。</p>
<pre><code>class Solution {
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    public int findPeak(int[] A) {
        // write your code here
        int start = 1, end = A.length-2; // 答案在之间
        while(start + 1 &lt;  end) {
            int mid = start + (end - start) / 2;
            if(A[mid] &lt; A[mid - 1]) {
                end = mid;
            } else if(A[mid] &lt; A[mid + 1]) {
                start = mid;
            } else {
                end = mid;
                // start = mid;  不影响结果
            }
        }
        if(A[start] &lt; A[end]) {
            return end;
        } else { 
            return start;
        }
    }
}
</code></pre><h3 id="first-bad-version">first-bad-version</h3>
<p>代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。</p>
<p>你可以通过 <code>isBadVersion</code> 的接口来判断版本号 version 是否在单元测试中出错，具体接口详情和调用方法请见代码的注释部分。</p>
<pre><code>/**
 * public class VersionControl {
 *     public static boolean isBadVersion(int k);
 * }
 * you can use VersionControl.isBadVersion(k) to judge whether 
 * the kth code version is bad or not.
*/
class Solution {
    /**
     * @param n: An integers.
     * @return: An integer which is the first bad version.
     */
    public int findFirstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (VersionControl.isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (VersionControl.isBadVersion(start)) {
            return start;
        }
        return end;
    }
}
</code></pre><h3 id="search-in-rotated-sorted-array">search-in-rotated-sorted-array</h3>
<p>假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。</p>
<p>你可以假设数组中不存在重复的元素。</p>
<pre><code>public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0)
            return -1;
        int start = 0;
        int end = A.length - 1;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) {
                return mid;
            }
            if (A[start] &lt; A[mid]) {
                // situation 1, red line
                if (A[start] &lt;= target &amp;&amp; target &lt;= A[mid]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else {
                // situation 2, green line
                if (A[mid] &lt;= target &amp;&amp; target &lt;= A[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (A[start] == target) {
            return start;
        }
        if (A[end] == target) {
            return end;
        }
        return -1;
    }
}
</code></pre><h3 id="search-for-a-range">search-for-a-range</h3>
<p>给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。</p>
<p>如果目标值不在数组中，则返回<code>[-1, -1]</code></p>
<pre><code>public class Solution {
    public int[] searchRange(int[] A, int target) {
        if (A.length == 0) {
            return new int[]{-1, -1};
        }

        int start, end, mid;
        int[] bound = new int[2]; 

        // search for left bound
        start = 0; 
        end = A.length - 1;
        while (start + 1 &lt; end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] &lt; target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[start] == target) {
            bound[0] = start;
        } else if (A[end] == target) {
            bound[0] = end;
        } else {
            bound[0] = bound[1] = -1;
            return bound;
        }

        // search for right bound
        start = 0;
        end = A.length - 1;
        while (start + 1 &lt; end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                start = mid;
            } else if (A[mid] &lt; target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] == target) {
            bound[1] = end;
        } else if (A[start] == target) {
            bound[1] = start;
        } else {
            bound[0] = bound[1] = -1;
            return bound;
        }

        return bound;
    }
}
</code></pre><h3 id="total-occurrence-of-target">total-occurrence-of-target</h3>
<p>给一个升序的数组，以及一个target，找到它在数组中出现的次数。</p>
<pre><code>public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int totalOccurrence(int[] A, int target) {
        // Write your code here
        if (A == null || A.length == 0) {
            return 0;
        }
        int start, end, mid;
        int first = 0;
        int last = 0;
        // search for first
        start = 0; 
        end = A.length - 1;
        while (start + 1 &lt; end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] &lt; target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[start] == target) {
            first = start;
        } else if (A[end] == target) {
            first = end;
        } else {
            return 0;
        }
        // search for last
        start = 0;
        end = A.length - 1;
        while (start + 1 &lt; end) {
            mid = start + (end - start) / 2;
            if (A[mid] == target) {
                start = mid;
            } else if (A[mid] &lt; target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] == target) {
            last = end;
        } else if (A[start] == target) {
            last = start;
        } else {
           return 0;
        }
        return (last - first + 1);
    }
}
</code></pre><h3 id="closest-number-in-sorted-array">closest-number-in-sorted-array</h3>
<p>在一个排好序的数组 A 中找到 i 使得 A[i] 最接近 target</p>
<pre><code>public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int closestNumber(int[] A, int target) {
        // Write your code here
        if (A == null || A.length == 0){
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (target == A[mid]) {
                end = mid;
            } else if (target &gt; A[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target - A[start] &lt;= A[end] - target) {
            return start;
        } else {
            return end;
        }
    }
}
</code></pre><h3 id="k-closest-numbers-in-sorted-array">k-closest-numbers-in-sorted-array</h3>
<p>给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在A中找与target最接近的k个整数。返回这k个数并按照与target的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。</p>
<pre><code>public class Solution {
    /**
     * @param A an integer array
     * @param target an integer
     * @param k a non-negative integer
     * @return an integer array
     */
    public int[] kClosestNumbers(int[] A, int target, int k) {
        // Write your code here
        int start = 0;
        int end = A.length - 1;
        int[] result = new int[k];
        int length = 0;
        if (A == null || A.length &lt; k){
            return result;
        }
        while (start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (target == A[mid]) {
                end = mid;
            } else if (target &gt; A[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        for (; length &lt; k &amp;&amp; start &gt;= 0 &amp;&amp; end &lt; A.length; length++){
            if (target - A[start] &lt;= A[end] - target) {
                result[length] = A[start];
                start--;
            } else {
                result[length] = A[end];
                end++;
            }
        }
        for (; length &lt; k; length++) {
            if (start &lt; 0) {
                result[length] = A[end];
                end++;
            } else if (end &gt; A.length - 1) {
                result[length] = A[start];
                start--;
            }
        }
        return result;
    }
}
</code></pre><h3 id="wood-cut">wood-cut</h3>
<p>有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。当然，我们希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度。</p>
<pre><code>public class Solution {
    /** 
     *@param L: Given n pieces of wood with length L[i]
     *@param k: An integer
     *return: The maximum length of the small pieces.
     */
    public int woodCut(int[] L, int k) {
        // write your code here
        if (L == null || L.length == 0 || k &lt; 0) {
            return 0;
        } 
        if (L.length == 1) {
            return  L[0] / k;
        }
        Arrays.sort(L);
        int start = 0;
        int end = L[L.length - 1];
        int mid = 0;
        int max = 0;
        while (start + 1 &lt; end) {
            mid = start + (end - start) / 2;
                int count = 0;
                for (int i : L) {
                    count += i / mid;
                }
                if (count &lt; k) {
                    end = mid;
                } else {
                    start = mid;
                    max = mid;
                }
        }
        return max;
    }
}
</code></pre><h3 id="sqrtx">sqrtx</h3>
<p>求一个数的平方根。</p>
<pre><code>public class Solution {
    public int sqrt(int x) {
        long lo = 0;
        long hi = x;

        while (hi &gt;= lo) {     
            long mid = lo+(hi-lo)/2;
            if (x &lt; mid * mid) {
                hi = mid-1;      // not hi = mid
            } else {
                lo = mid+1;  
            }
        }
        return (int) hi;
    }
}
</code></pre><h3 id="参考资料">参考资料</h3>
<p><a href="http://www.jiuzhang.com/?referer=38beb6">九章算法</a></p>

            <hr/>
            <div style="padding: 0; margin: 10px auto; width: 90%; text-align: center">
                <button id="rewardButton" , disable="enable" ,
                        onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}"
                        ,
                        style="cursor: pointer; border: 0; outline: 0; border-radius: 100%; padding: 0; margin: 0; letter-spacing: normal; text-transform: none; text-indent: 0px; text-shadow: none">
                    <span style="display: inline-block; width: 60px; height: 60px; border-radius: 100%; line-height: 58px; color: #fff; font-size:36px; font-family: 'Palatino Linotype', 'Book Antiqua', Palatino, Helvetica, STKaiti, SimSun, serif; background: rgb(236,96,0)">赞</span>
                </button>
                <div id="QR" style="display: none;">
                    <p><img src="../images/weixin.jpeg" width="200" /></p>
                    <p><img src="../images/zhifubao.jpeg" width="200" /></p>
                </div>

            </div>
            <h3>评论</h3>
            <div id="vcomment"></div>
        </div>
        <div class="col-md-1"></div>
    </div>
</div>

<div class="row" style="padding-top: 60px">
    <div class="container center-block">
        <div class="col-md-1"></div>
        <div class="col-md-10 col-sm-12">
            <div class="ds-thread"
                 data-thread-key=5871f495d2f092c392ca4d54
                 data-title= 算法之美——二分法
                 data-url=binarysearch>
            </div>
        </div>
        <div class="col-md-1"></div>
    </div>
</div>

<div class="footer">
    <a href="https://www.bcmeng.com/" target="_blank"  rel="nofollow">康凯森</a>
</div>

<script src="../js/code.js"></script>
<script>hljs.initHighlightingOnLoad();</script>
<script src="../js/jquery.min.js"></script>
<script src="../js/bootstrap.js"></script>
<script>
    var _hmt = _hmt || [];
    (function() {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?1d198a377ef466190881d1c021155925";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
    })();
</script>
<script src="../js/av-min.js"></script>
<script src='../js/Valine.min.js'></script>
<script type="text/javascript">
    window.valine = new Valine({
        el: '#vcomment' ,
        verify: true,
        notify: true,
        appId: 'BlLnB0re5OzQVzrgEplAxkyg-gzGzoHsz',
        appKey: 'wUyxSV0U4Vi7oK1EHK6ipErv',
        placeholder: '欢迎评论'
    });
</script>

</body>
</html>